1. Field of the Invention
The present invention generally relates to data storage systems, networks, and methods that efficiently manage disk block allocation and back-up operations.
2. Description of Related Art
With increasing reliance on electronic means of data communication, different models to efficiently and economically store a large amount of data have been proposed. A data or file storage mechanism requires not only a sufficient amount of physical storage space to store data, but techniques for managing data storage. For example, file storage systems may maintain a block map to keep track of consumed and free space. Some keep a simple counter per block, while others maintain segment list data structures made up of a block number and a length of the segment.
In addition, data storage systems are provided with a level of fault tolerance or redundancy (depending on how critical the data is) to preserve data integrity in the event of one or more disk failures. Data recovery may also be needed in the event a file is accidentally deleted or corrupted. One way of providing fault tolerance is to periodically back up various directories, files, and related information stored in the data storage system to a secondary storage system, such as a tape drive or tape library, to thereby capture the file data for recovery purposes in the event that a disk failure occurs in the system. When constructing the system backup, it is useful to be able to back up a self-consistent image of the directories, files, and related information as it appears at a single point in time, without the need to halt or quiesce activity in the directories and files. One way to perform this is by constructing an image or “snapshot.” A snapshot is a copy of a set of files and/or directories and related data as they are at specific point in time. A snapshot may be based on a set of files and directories or on a set of blocks on a storage device. Snapshot images are also useful for allowing recovery of accidentally deleted or corrupted files without resorting to an offline backup copy, stored for example on a tape.
Snapshots offer a fast and computationally-inexpensive backup scheme. For example, snapshots may take advantage of a copy-on-write semantic for blocks. In Unix file systems, snapshots can be implemented using inodes—data structures that contain information about the files stored in the file system—and the simple counter for the per-block structure noted above. For example, taking a snapshot in such a system involves allocating a new inode for the snapshot, pointing the inode at the same directory inode of the original volume, and incrementing the counter on which the directory inode resides. This results in the original volume and the snapshot sharing all of the data blocks allocated to the original volume, except for the top-level directory inode block.
Modifying contents of the original volume after the snapshot is taken results in propagating the incremented counter to a layer beneath it in the file system tree. When this occurs, the old contents of the block are referenced only by the snapshot, and a new block is allocated for the modification. While this scheme makes taking snapshots very fast, it requires a potentially very expensive operation to delete a snapshot, since every inode in the snapshot must be examined to determine what blocks it references, so their respective reference counts may be decremented. For example, each counter associated with the snapshot's namespace would be accessed and decremented in order to delete the snapshot. The current snapshot technique also limits the number of snapshots by the width of the counter used to track the number of references to a block. Typically, an 8-bit counter is used, thus limiting the system to roughly 250 snapshots. It is also difficult with this technique to determine how much capacity would be recovered by deleting one or more particular snapshots (i.e., how many blocks are uniquely addressed only by these snapshots), without performing a full traversal of the snapshot (equivalent to that required when deleting it), which is a lengthy operation.